package edu.rit.checkers;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 * 
 * @author Ian Tewksbury (ict8574@rit.edu)
 */
public class ConfigTree {
	
	
	private ConfigNode root;
	public int maxDepth;
	public SortedSet<ConfigNode> unassignedNodes;
	private List<ConfigNode> maxDepthNodes;
	private long addedNodes;
	private long prunedNodes;
	private int currDepth;
	private double alphaBetaScore;
	
	/**
	 * 
	 * @param initMaxDepth
	 * @param rootValue
	 */
	public ConfigTree(int initMaxDepth, ConfigNode rootValue, boolean rootAssigned) {
		this.root = rootValue;
		this.maxDepth = initMaxDepth;
		this.addedNodes = 0;
		this.prunedNodes = 0;
		this.currDepth = this.root.depth;
		this.alphaBetaScore = 0;
		
		this.unassignedNodes = new TreeSet<ConfigNode>(
			/**
			 * When assigning nodes assign the top left most unassigned node
			 */
			new Comparator<ConfigNode>() {
				public int compare(ConfigNode o1, ConfigNode o2) {
					//Assign highest nodes first
					int retVal = o1.depth - o2.depth;
					if(retVal == 0) {
						//explore furtherest left nodes first
						retVal = o1.nodeNum - o2.nodeNum;
					}
					
					return retVal;
				}
				
			});
		
		if(!rootAssigned) {
			this.unassignedNodes.add(root);
		}
		this.maxDepthNodes = new ArrayList<ConfigNode>(1000000);
	}
	
	/**
	 * 
	 * @param localTree
	 */
	public synchronized void mergeTree(ConfigTree localTree) {
		this.unassignedNodes.addAll(localTree.unassignedNodes);
		this.maxDepthNodes.addAll(localTree.maxDepthNodes);
		this.addedNodes += localTree.addedNodes;
	}
	
	/**
	 * 
	 * 
	 * @param nodes
	 * @param parent
	 * @return
	 * @throws TreeException 
	 */
	public  boolean addNodes(List<ConfigNode> nodes, boolean isAssigned) {
		boolean allAdded = true;
		
		for(ConfigNode node : nodes) {
			allAdded = allAdded && this.addNode(node, isAssigned);
		}
		
		return allAdded;
	}
	
	/**
	 * 
	 * 
	 * @param nodes
	 * @param parent
	 * @return
	 * @throws TreeException 
	 */
	public  boolean addNodes(Set<ConfigNode> nodes, boolean isAssigned) {
		boolean allAdded = true;
		
		for(ConfigNode node : nodes) {
			allAdded = allAdded && this.addNode(node, isAssigned);
		}
		
		return allAdded;
	}
	
	/**
	 * NOTE: if root not set yet then nothing gets added
	 * 
	 * @param nodes
	 * @param parent
	 * @return
	 * @throws TreeException 
	 */
	public boolean addNode(ConfigNode node, boolean isAssigned) {
		boolean added = false;
		
		if(node.depth <= this.maxDepth) {
			added = true;
			//update stuff
			this.updateCurrDepth(node);
			++this.addedNodes;
			
			if(node.depth == this.maxDepth) {
				added = false;
				this.maxDepthNodes.add(node);
			} else if(!isAssigned) {
				synchronized (this.unassignedNodes) {
					this.unassignedNodes.add(node);
				}
			}
		}
		
		return added;
	}
	
	/**
	 * 
	 * @return
	 */
	public  ConfigNode getNextUnassignedNode() {
		ConfigNode retVal = null;
		
		synchronized (this.unassignedNodes) {
			//multiple threads could ask root tree for an unassigned node
			if(this.hasUnassignedNodes()) {
				retVal = this.unassignedNodes.first();
				this.unassignedNodes.remove(retVal);
			}
		}

		return retVal;
	}
	
	/**
	 * 
	 * @return
	 */
	public boolean hasUnassignedNodes() {
		return !this.unassignedNodes.isEmpty();
	}
	
	/**
	 * 
	 * @return
	 */
	public long addedNodes() {
		return this.addedNodes;
	}
	
	/**
	 * 
	 * @return
	 */
	public long size() {
		return this.addedNodes - this.prunedNodes;
	}
	
	/**
	 * 
	 * @return
	 */
	public int getCurrDepth() {
		return this.currDepth;
	}
	
	/**
	 * 
	 * @return
	 */
	public long getPrunedNodes() {
		return this.prunedNodes;
	}
	
	/**
	 * 
	 * @return
	 */
	public double getLastAlphaBetaScore() {
		return this.alphaBetaScore;
	}
	
	/**
	 * 
	 * @param increaseAmount
	 */
	public  void increaseMaxDepth(int increaseAmount) {
		this.maxDepth += increaseAmount;
		this.unassignedNodes.addAll(this.maxDepthNodes);
		this.maxDepthNodes.clear();
	}
	
	@Override
	public String toString() {
		String s = "Tree:";
		s += "\n  Depth:";
		s += "\n    Max: " + this.maxDepth;
		s += "\n    Current: " + this.getCurrDepth();
		s += "\n  Size: " + this.size();
		s += "\n    Added Nodes: " + this.addedNodes();
		s += "\n    Pruned Nodes: " + this.getPrunedNodes();
		s += "\n  Unnassigned Nodes: " + this.unassignedNodes.size();
		s += "\n  Max Depth Nodes: " + this.maxDepthNodes.size();
		s += "\n  Last Alpha-Beta Score: " + this.getLastAlphaBetaScore();
		
		return s;
	}
	
	/**
	 * 
	 */
	public  void alphaBeta() {
		this.alphaBetaScore = 
			alphaBeta(this.root, Double.NEGATIVE_INFINITY,
					Double.POSITIVE_INFINITY, this.maxDepth);
	}
	
	/**
	 * 
	 * @param currNode
	 * @param alpha
	 * @param beta
	 * @param maxDepth
	 * @return
	 */
	private double alphaBeta(ConfigNode currNode, double alpha, double beta,
		int maxDepth) {
		
		List<ConfigNode> children = currNode.children;
		Collections.sort(children,
			/**
			 * Comparator to place high scores first for A-B optimization
			 */
			new Comparator<ConfigNode>() {
				/**
				 * 
				 * @param o1
				 * @param o2
				 * @return
				 */
				public int compare(ConfigNode o1, ConfigNode o2) {
					return o2.getScore() - o1.getScore();
				}
			}
		);
		
		//if at max depth or game over (either winning player or no possible
		//	moves) then return score of move
		if(currNode.depth == maxDepth || children.isEmpty() ||
			currNode.isFinalConfig()) {

			return currNode.getScore();
		}
		
		double score;
		boolean cutOff = false;
		List<ConfigNode> cutOffChildren = new ArrayList<ConfigNode>();
		//if max's turn
		if(currNode.getPlayer() == 2) {
			double newAlpha = alpha;
			for(ConfigNode childNode : children) {
				if(!cutOff) {
					score = alphaBeta(childNode, newAlpha, beta, maxDepth);
					if(score > newAlpha) {
						newAlpha = score; //we found better move
					}
					if(newAlpha >= beta) {
						cutOff = true;
					}
				} else {
					cutOffChildren.add(childNode);
				}
			}
			
			//we are cutting off all unneeded children
			this.removeChildren(currNode, cutOffChildren);
			
			return newAlpha; //our best move
		//if min's turn
		} else {
			double newBeta = beta;
			for(ConfigNode childNode : children) {
				if(!cutOff) {
					score = alphaBeta(childNode, alpha, newBeta, maxDepth);
					if(score < newBeta) {
						newBeta = score; //opponent found better move
					}
					if(alpha >= newBeta) {
						cutOff = true;
					}
				} else {
					cutOffChildren.add(childNode);
				}
			}
			
			//we are cutting off all unneeded children
			this.removeChildren(currNode, cutOffChildren);
			
			return newBeta; //opponents best move
		}
	}
	
	/**
	 * 
	 * @param node
	 */
	private void updateCurrDepth(ConfigNode node) {
		if(node.depth > this.currDepth) {
			this.currDepth = node.depth;
		}
	}
	
	/**
	 * 
	 * @param parent
	 * @param children
	 */
	private void removeChildren(ConfigNode parent,
		List<ConfigNode> children) {
		
		if(parent.depth+1 < this.maxDepth) {
			this.prunedNodes += children.size();
		}
			
		for(ConfigNode child : children) {		
			//remove from unassigned nodes and max depth nodes if it is there
			this.unassignedNodes.remove(child);
			this.maxDepthNodes.remove(child);
			
			//have to recursively remove all children
			this.removeChildren(child, child.children);
		}
		
		//remove from parent
		parent.children.removeAll(children);
	}
}
